import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by L.jp
 * Description:n皇后问题 研究的是如何将 n个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 *
 * 给你一个整数 n ，返回所有不同的n皇后问题 的解决方案。
 *
 * 每一种解法包含一个不同的n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

 * User: 86189
 * Date: 2021-11-28
 * Time: 19:45
 */
//皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
public class QueenN {
    static List<List<String>> list=new ArrayList<>();
    public static void dfs(int n,int curRow,char[][] chessboard){
        if(curRow==n){//深度搜索（递归）的深度如果等于了棋盘的深度那么说明执行到了最后一行情况，是符合的，可以把这个棋盘的情况加入到List
            list.add(tmpList(chessboard));
            return;
        }
        for(int curCol=0;curCol<n;curCol++){
            if(isOccupied(curRow,curCol,n,chessboard)){
                chessboard[curRow][curCol]='Q';//如果符合条件，不会形成皇后攻击，那么就可以在这个坐标放一个皇后
                dfs(n,curRow+1,chessboard);//深搜下一行，判断下一行是否可以放皇后
                chessboard[curRow][curCol]='.';//当满足情况时，会返回到这里，需要把当前放皇后这个位置置为空，进行下一轮判断
            }
        }
    }
    public  static  List tmpList(char[][] chessboard){
        List<String> tmp=new ArrayList<>();
        for(char[] ch:chessboard){//对于棋盘是一个字符的二维矩阵
            tmp.add(String.copyValueOf(ch));//要把符合情况的每一行的字符数组变成字符串，然后把每一行的情况加入到临时列表中，表示完整的一个棋盘
        }
        return tmp;

    }
    //排除同列，同45度斜线，同135度斜线有皇后的情况，行的情况已经在递归的时候解决了
    public static  boolean isOccupied(int curRow,int curCol,int n,char[][] chessboard){
        //判断列的情况
        for(int i=0;i<curRow;i++){
            if(chessboard[i][curCol]=='Q')
                return  false;
        }
        //判断45度斜线的情况
        for(int i=curRow-1, j=curCol-1;i>=0 && j>=0;i--,j--){
            if(chessboard[i][j]=='Q')
                return false;
        }
        //判断135度斜线
        for(int i=curRow-1, j=curCol+1;i>=0 && j<n;i--,j++){
            if(chessboard[i][j]=='Q')
                return false;
        }
        return true;
    }
    public static List<List<String>> solveNQueens(int n) {
        char[][] chessboard=new char[n][n];//定义棋盘
        for(char[] chess:chessboard){
            Arrays.fill(chess,'.');//'.'表示空，先把棋盘每个位置置为空
        }
        dfs(n,0,chessboard);//从第一行开始判断
        return list;
    }

    public static void main(String[] args) {
        int n=4;
        System.out.println(solveNQueens(n));
    }
}
